package 分治;

/**
 * @description:
 * @author: ywk 第一个重复的数组
 * @date: 2021-03-02
 */
public class 寻找第一个或者最后重复的数组 {
    //二分搜索
    public static void BinarySearchFirstOccurrence(int[] arr, int low, int high, int data) {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == data && low == mid || arr[mid] == data && arr[mid - 1] < data) {
                System.out.println(mid);
                return;
            }
            if (arr[mid] >= data) {
                BinarySearchFirstOccurrence(arr, low, mid - 1, data);
            } else {
                BinarySearchFirstOccurrence(arr, mid + 1, high, data);
            }
        }
    }

    public static void BinarySearchLastOccurrence(int[] arr, int low, int high, int data) {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == data && high == mid || arr[mid] == data && arr[mid + 1] > data) {
                System.out.println(mid);
                return;
            }
            if (arr[mid] <= data) {
                BinarySearchLastOccurrence(arr, mid + 1, high, data);
            } else {
                BinarySearchLastOccurrence(arr, low, mid - 1, data);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 4, 5};
        BinarySearchFirstOccurrence(arr, 0, arr.length, 2);
        BinarySearchLastOccurrence(arr, 0, arr.length, 2);
    }
}